package com.qch.edu.sort.tongSort;

import java.util.Arrays;

/**
 * @Author qch
 * @Date 2021/3/6
 * 计数排序（桶排序的一种->非比较排序）：稳定，时间O(n+k)，空间O(n+k),k指出现的种类
 * 思想：每个数出现了多少次，以这个数为下标值，每出现一次给他加一
 * 应用范围：量大但是范围小
 * eg1:某大型企业数万名员工工龄排序
 * eg2:如何快速得知高考的名次
 * 开得较多
 */
public class JishuCountSort {
    public static void main(String[] args) {
        int[] arr={2,4,2,4,7,1,1,5,6,8,8,4,9,0,3,2,2};
        int[] sort = sort(arr);
        System.out.println(Arrays.toString(sort));
    }

    /**
     * 1.毛病：1w个数，但是范围是100到150，然后好多浪费了-》映射到[0,50]
     * 2.不稳定：将排序算法编程稳定（person(age,sex)）->累加数组
     * @param arr
     * @return
     */
    static int[] sort(int[] arr){
        int[] result=new int[arr.length];
        int[] count=new int[10];
        for (int i = 0; i < arr.length; i++) {
            count[arr[i]]++;
        }
        System.out.println(Arrays.toString(count));
        //不稳定
        /*for (int i=0,j = 0; i< count.length; i++) {
            while (count[i]-->0)result[j++]=i;
        }*/
        //改进
        for (int i = 1; i < count.length; i++) {
            count[i]=count[i]+count[i-1];
        }
        //处数组[1, 2, 4, 1, 3, 1, 1, 1, 2, 1]
        //累加数组[1, 3, 7, 8, 11, 12, 13, 14, 16, 17]
        //1代表0出现的次数，3代表1的最后一个下表，6代表2出现的最后一个下标
        //然后[2,4,2,4,7,1,1,5,6,8,8,4,9,0,3,2,2]
        //最后一个2放在a[7-1],7一直减减，倒数第二个2放在a[7-2]的位置上，知道7减到0，此时，2个2的相对位置没有发生变化-》所以这个算法是稳定的
        System.out.println(Arrays.toString(count));
        //对原来的数组倒序迭代
        for (int i = arr.length - 1; i >= 0; i--) {
            result[--count[arr[i]]]=arr[i];
        }
        return result;
    }
}
